public class RecursiveBinarySearch
{
    public static final int NOT_FOUND = -1;

    public static int binarySearch( Comparable [ ] a, Comparable x,
                                         int low, int high )
    {
        if (low > high)
            return NOT_FOUND;
        
        int mid = ( low + high ) / 2;
        
        if( a[ mid ].compareTo( x ) < 0 )
			return binarySearch(a, x, mid + 1, high);
        else if( a[ mid ].compareTo( x ) > 0 )
			return binarySearch(a, x, low, mid - 1);
        else
            return mid;
    }

    // Test program
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [] a = new Integer [SIZE];
        
        for( int i=0; i < SIZE; i++) {
            a[i] = new Integer(i * 2);
        }

        System.out.println("Found 8 at " +
							 binarySearch(a, new Integer(8), 0, a.length - 1));
        System.out.println("Found 9 at " +
							 binarySearch(a, new Integer(9), 0, a.length - 1));

    }
}